This video introduces us to sort() function in C++ STL and how it is implemented in Arrays and Vectors. We will also discuss the time complexities of the function.
Codes:
- Code(Array)
- Code(Vector)
- Code(Own Object & Order)
This track of the course covers the topic "Sorting".
In details, this track will cover:
Objective: The objective of this track is to familiarize the learners with Sorting Algorithms.
Track Content:
Assessment: All Tracks in every week are associated with weekly contests.
This video introduces us to sort() function in C++ STL and how it is implemented in Arrays and Vectors. We will also discuss the time complexities of the function.
Codes:
This video introduces us to Sorting in Java. We will also be learning about Arrays.sort and Collections.sort in the two upcoming lectures in detail.
This video talks about the sort() function of the Arrays class in Java, along with the few more important functions of Arrays class in Java.
Codes:
This video introduces us to the techniques of sorting various collections using the sort() function in Java.
Codes:
This video analyses the stability of various sorting algorithms.
Explanation and implementation of Bubble Sort.
Explanation and implementation of Selection Sort.
This video talks about Insertion Sort along with its working and time complexities.
Codes:
This is an introductory lecture to the Merge Sort algorithm.
In this video, we will take two sorted arrays and merge them.
Codes:
This video is a complex version of the previously discussed problem on Merge Sort. Here we take a single array with three points namely, the lower, the middle and the highest point. The elements from the lower to the middle are sorted and the elements from the (middle+1) to the higher are sorted. The task is to merge these two sorted parts into one.
Codes:
Merge Sorting Algorithm
Codes:
This video analyses the merge sort algorithm explaining its working and the time complexity involved in the Sorting algorithm.
This video discusses a problem taking two sorted arrays and picking out the intersection elements from the two arrays.
Codes:
This video discusses a problem taking two sorted arrays and printing the union of the two arrays.
Codes:
This video discusses the problem of taking an unsorted array and counting the inversions in it. There are two conditions for the elements to be inverse:
This video introduces us to the Partition method of Quick Sort. This partitioning method is a naive way of approach towards partitioning an array.
Codes:
This video introduces us to Lomuto Partition which is another method of partitioning. In this method, the traversal is done only once with a constant space complexity.
Codes:
This video introduces us to Hoare Partition which is another method of partitioning. This is better than the previously discussed Partitioning method. This method takes constant space and O(n) time for partitioning. It also travels the input array only once.
Codes:
This video introduces us to the QuickSort algorithm and all the key points revolving around this sorting algorithm.
This video explains in detail the QuickSort using the method of Lomuto Partition.
Codes:
This video explains in detail the QuickSort using the method of Hoare Partition.
Codes:
This video analyses the QuickSort Algorithm in detail explaining the working and time complexity.
This video analyses the Space Analysis of QuickSort Algorithm.
This video analyses and explains the point of the choice of pivot in QuickSort Algorithm and the worst-case scenario of QuickSort Algorithm.
This video talks about the Tail call elimination QuickSort Algorithm.
Code:
This video discusses a problem which involves finding the Kth smallest element from a given array.
Codes:
This video discusses the famous Chocolate Distribution Problem based on a few rules.
Codes:
This video discusses a famous interview problem in which you need to segregate an array of elements containing two types of elements. The types are:
This video discusses a famous interview problem in which you need to segregate an array of elements containing three types of elements. The types are:
This video discusses the problem of overlapping the merged intervals.
Codes:
you are given arrival and departure times of the guests, you need to find the time to go to the pary so that you can meet maximum people.
Codes:
This video discusses the Cycle Sort algorithm, its working and analyses the time and space complexity.
Codes:
Working of Heap Sort with implementation.
Codes:
This video talks about Counting Sort, a linear time sorting algorithm for limited range elements.
Codes:
Explanation and implementation fo Radix Sort
Codes:
This video talks about standard Bucket Sort algorithm and its applications.
Codes:
This video discusses the overview of Sorting Algorithm in general.

Step 1: If the current element is 1st element of array,
it is already sorted.
Step 2: Pick next element
Step 3: Compare the current element will all elements
in the sorted sub-array before it.
Step 4: Shift all of the elements in the sub-array before
the current element which are greater than the current
element by one place and insert the current element
at the new empty space.
Step 5: Repeat step 2-3 until the entire array is sorted.
In one iteration if we swap all adjacent elements of an array such that after swap the first element is less than the second element then at the end of the iteration, the first element of the array will be the minimum element.
arr[] = 64 25 12 22 11.
// Find the minimum element in arr[0...4]
// and place it at beginning
11 25 12 22 64
// Find the minimum element in arr[1...4]
// and place it at beginning of arr[1...4]
11 12 25 22 64
// Find the minimum element in arr[2...4]
// and place it at beginning of arr[2...4]
11 12 22 25 64
// Find the minimum element in arr[3...4]
// and place it at beginning of arr[3...4]
11 12 22 25 64
/* low --> Starting index, high --> Ending index */
quickSort(arr[], low, high)
{
if (low < high)
{
/* pi is partitioning index, arr[pi] is now
at right place */
pi = partition(arr, low, high);
quickSort(arr, low, pi - 1); // Before pi
quickSort(arr, pi + 1, high); // After pi
}
}
/* low --> Starting index, high --> Ending index */
quickSort(arr[], low, high)
{
if (low < high)
{
/* pi is partitioning index, arr[pi] is now
at right place */
pi = partition(arr, low, high);
quickSort(arr, low, pi - 1); // Before pi
quickSort(arr, pi + 1, high); // After pi
}
}
/* This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */
partition (arr[], low, high)
{
// pivot (Element to be placed at right position)
pivot = arr[high];
i = (low - 1) // Index of smaller element
for (j = low; j <= high- 1; j++)
{
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot)
{
i++; // increment index of smaller element
swap arr[i] and arr[j]
}
}
swap arr[i + 1] and arr[high])
return (i + 1)
}
arr[] = {10, 80, 30, 90, 40, 50, 70}
Indexes: 0 1 2 3 4 5 6
low = 0, high = 6, pivot = arr[h] = 70
Initialize index of smaller element, i = -1
Traverse elements from j = low to high-1
j = 0 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 0
arr[] = {10, 80, 30, 90, 40, 50, 70} // No change as i and j
// are same
j = 1 : Since arr[j] > pivot, do nothing
// No change in i and arr[]
j = 2 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 1
arr[] = {10, 30, 80, 90, 40, 50, 70} // We swap 80 and 30
j = 3 : Since arr[j] > pivot, do nothing
// No change in i and arr[]
j = 4 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 2
arr[] = {10, 30, 40, 90, 80, 50, 70} // 80 and 40 Swapped
j = 5 : Since arr[j] <= pivot, do i++ and swap arr[i] with arr[j]
i = 3
arr[] = {10, 30, 40, 50, 80, 90, 70} // 90 and 50 Swapped
We come out of loop because j is now equal to high-1.
Finally we place pivot at correct position by swapping
arr[i+1] and arr[high] (or pivot)
arr[] = {10, 30, 40, 50, 70, 90, 80} // 80 and 70 Swapped
Now 70 is at its correct place. All elements smaller than
70 are before it and all elements greater than 70 are after
it.
T(n) = T(k) + T(n-k-1) + Θ(n)The first two terms are for two recursive calls, the last term is for the partition process. k is the number of elements which are smaller than pivot.
T(n) = T(0) + T(n-1) + Θ(n)The solution of above recurrence is Θ(n2).
which is equivalent to
T(n) = T(n-1) + Θ(n)
T(n) = 2T(n/2) + Θ(n)The solution of above recurrence is Θ(nLogn). It can be solved using case 2 of Master Theorem.
T(n) = T(n/9) + T(9n/10) + Θ(n)Solution of above recurrence is also O(nLogn)
MergeSort(arr[], l, r)
If r > l
1. Find the middle point to divide the array into two halves:
middle m = (l+r)/2
2. Call mergeSort for first half:
Call mergeSort(arr, l, m)
3. Call mergeSort for second half:
Call mergeSort(arr, m+1, r)
4. Merge the two halves sorted in step 2 and 3:
Call merge(arr, l, m, r)

For simplicity, consider the data in the range 0 to 9.
Input data: 1, 4, 1, 2, 7, 5, 2
1) Take a count array to store the count of each unique object.
Index: 0 1 2 3 4 5 6 7 8 9
Count: 0 2 2 0 1 1 0 1 0 0
2) Modify the count array such that each element at each index
stores the sum of previous counts.
Index: 0 1 2 3 4 5 6 7 8 9
Count: 0 2 4 4 5 6 6 7 7 7
The modified count array indicates the position of each object in
the output sequence.
3) Output each object from the input sequence followed by
decreasing its count by 1.
Process the input data: 1, 4, 1, 2, 7, 5, 2. Position of 1 is 2.
Put data 1 at index 2 in output. Decrease count by 1 to place
next data 1 at an index 1 smaller than this index.
Input data: [4, 10, 3, 5, 1]
4(0)
/ \
10(1) 3(2)
/ \
5(3) 1(4)
The numbers in bracket represent the indices in the array
representation of data.
Applying heapify procedure to index 1:
4(0)
/ \
10(1) 3(2)
/ \
5(3) 1(4)
Applying heapify procedure to index 0:
10(0)
/ \
5(1) 3(2)
/ \
4(3) 1(4)
The heapify procedure calls itself recursively to build heap
in top down manner.
sort(arr, arr+n);
Here, arr is the name or base address of the array
and, n is the size of the array.
sort(vec.begin(), vec.end());
Here, vec is the name of the vector.
Array after sorting is :
0 1 2 3 4 5 6 7 8 9
Vector after sorting is :
1 2 3 4 5
Array after sorting :
9 8 7 6 5 4 3 2 1 0
Intervals sorted by start time :
[1,9] [2,4] [4,7] [6,8]
public static void sort(int[] arr, int from_Index, int to_Index)
arr - The array to be sorted.
from_Index - The index of the first element, inclusive, to be sorted.
to_Index - The index of the last element, exclusive, to be sorted.
Modified arr[] : [6, 7, 9, 13, 21, 45, 101, 102]
Modified arr[] : [13, 6, 7, 21, 45, 9, 2, 100]
Modified arr[] : [100, 45, 21, 13, 9, 7, 6, 2]
Modified arr[] :
[code 1="practice.geeksforgeeks.org," 2="quiz.geeksforgeeks.org" language=".geeksforgeeks.org,"][/code]
Modified arr[] :
[quiz.geeksforgeeks.org, practice.geeksforgeeks.org, code.geeksforgeeks.org]
3 12
5 7
10 20
public static void sort(List myList)
myList : A List type object we want to sort.
This method doesn't return anything
Let us suppose that our list contains
{"Geeks For Geeks", "Friends", "Dear", "Is", "Superb"}
After using Collection.sort(), we obtain a sorted list as
{"Dear", "Friends", "Geeks For Geeks", "Is", "Superb"}
List after the use of Collection.sort() :
[Dear, Friends, Geeks For Geeks, Is, Superb]
List after the use of Collection.sort() :
[Superb, Is, Geeks For Geeks, Friends, Dear]
Unsorted
111 bbbb london
131 aaaa nyc
121 cccc jaipur
Sorted by rollno
111 bbbb london
121 cccc jaipur
131 aaaa nyc
A | Recurrence is T(n) = T(n-2) + O(n) and time complexity is O(n^2) |
B | Recurrence is T(n) = T(n-1) + O(n) and time complexity is O(n^2) |
C | Recurrence is T(n) = 2T(n/2) + O(n) and time complexity is O(nLogn) |
D | Recurrence is T(n) = T(n/10) + T(9n/10) + O(n) and time complexity is O(nLogn) |